1. Field of the Invention
The present invention generally relates to network routing, and relates more particularly to the fair allocation of resources in a multilink point-to-point protocol (PPP) bundle.
2. Description of the Related Art
Modern data communications utilize a variety of different forms of packet communications. Within a packet network, many of the links are point-to-point links between peer nodes. When a need for increased bandwidth on such a link arises, one option is to replace the existing link with a higher bandwidth link. However, this approach often is prohibitively expensive, particularly as an incremental upgrade. Accordingly, the solution to providing increased bandwidth often entails deploying one or more new links of similar or somewhat higher capacity in parallel to the existing link between the nodes forming the two end points. Such an upgrade forms a multilink bundle, with an aggregate bandwidth that is essentially the sum of the bandwidths or throughput rates of the parallel links in the bundle.
The multilink bundle does offer increased capacity; however, its use presents certain problems. To utilize the links in the bundle effectively as an aggregate requires that the bundle effectively appear as a single interface to each end-point node. At one logical level, traffic intended for transport through this interface must appear as a single, unified data stream. However, within the bundle, it is necessary to segregate the traffic and distribute segments of traffic to the different links.
To maximize utilization of the parallel links within a multilink bundle, the packet communication load on the two or more parallel links are “balanced,” that is to say the volume of packet data traffic through the bundle must be optimally distributed between the various parallel links. A number of known algorithms are used to select which link to use to transport the various packets between the end-points and thereby balance the load on the links.
One type of approach manages the packet routing over the links based on link utilization. For example, when traffic on a first link reaches a certain level, the sending node shifts further packet traffic over to the next parallel link. This approach tends to load one link first, then another, and so on. Another general class of load-balancing techniques evenly distributes packets across all the links regardless of the current level of utilization of any particular link. This later approach reduces packet latency. Within this class, there are a number of specific approaches to load balancing.
Many point-to-point links today use PPP, the Point-to-Point Protocol. RFC1717, “The Multilink Protocol (MP),” which is incorporated by reference herein in its entirety for all purposes, defines a standardized extension of the PPP, which enables combination of PPP links or channels into a “Multilink bundle” for higher rate point-to-point communications. The Multilink Protocol (MP) uses packet fragmentation and a round-robin link assignment technique to distribute portions of data traffic over the various links within a bundle.
A typical load-balancing situation using the Multilink Protocol involves a point-to-point bundle of links between two peers, for example, between two routers. A common implementation may use multiple ISDN links between the nodes, for example basic rate or primary rate (T1) ISDN connections. A router at one end of the bundle separates a long Internet Protocol (IP) packet into two or more fragments and adds an MP sequence header to each fragment. The load-balancing algorithm distributes the fragments taken from each packet over an appropriate number of the links, to allow parallel transmission through the bundle. In this manner, packets from a particular flow actually utilize any or all of the links in the bundle.
The communications over parallel links may encounter different delays in transmission. Fragments of one packet or succeeding packets may arrive at the receiver in a different order than when sent out over the multilink bundle. The PPP Multilink Protocol therefore uses packet sequencing to order fragments and packets. Specifically, a sequence number included in the header of each fragment of a packet allows the receiver to reorder the fragments and packets properly as they arrive over different links in the bundle. The use of the sequence numbers, the differences in transit time through the links and the subsequent reordering all add delay and processing time.
During fragment reassembly, it may be discovered that one of the fragments is missing. Accordingly, the packet cannot be fully reconstructed and all of the fragments of that packet should be dropped. Multilink PPP fragment reassembly algorithms depend on heuristic measures to aid in dropping fragments received on a link when others that are part of the whole packet do not arrive in time on one or more of the constituent links.
RFC 1990, “The PPP Multilink Protocol (MP),” which is incorporated herein by reference in its entirety for all purposes, suggests one heuristic to detect fragment loss on a Multilink PPP bundle. The heuristic detects fragment loss based on the assumption that either a fragment with (E)nd bit that is part of an incomplete packet is present or a fragment with (B)egin bit following an incomplete packet is present. If neither of these conditions matches for a sequence of one or more packets, such packet loss will not be detected. This heuristic measure, only helps in saving some processing cycles, but may not detect the fragment loss at an early time. This could mean that for the duration for which the fragments are outstanding, resources will be locked out. Lack of a good method to detect and stop resource usage on miscreant bundles, could lead to system-wide resource crunch that could affect the other benign bundles.